package DataStructuresTest.BinaryTree;

import sun.plugin2.ipc.windows.WindowsIPCFactory;

import java.nio.BufferUnderflowException;
import java.util.Comparator;

public class BinarySearchTree<AnyType>{
    private static class BinaryNode<AnyType>{
        BinaryNode(AnyType theElement){this( theElement,null,null);}

        BinaryNode(AnyType theElement,BinaryNode<AnyType> lt,BinaryNode<AnyType> rt)
        {element = theElement;left = lt;right = rt;}
        AnyType element;
        BinaryNode<AnyType> left;
        BinaryNode<AnyType> right;
    }

    private BinaryNode<AnyType> root;
    private Comparator<? super AnyType> cmp;

    public BinarySearchTree(){root = null;}
    public BinarySearchTree(Comparator<? super AnyType> c){ root = null;cmp = c; }

    private int myCompare(AnyType lhs,AnyType rhs){
        if (cmp != null)
            return cmp.compare(lhs,rhs);
        else
            return ((Comparable)lhs).compareTo(rhs);
    }

    public void makeEmpty(){root = null;}
    public boolean isEmpty(){return root == null;}

    public boolean contains(AnyType x){return contains(x,root);}

    public AnyType findMin(){
        if (isEmpty())throw new BufferUnderflowException();
        return findMin(root).element;
    }
    /**
     * internal method to find the smallest item in a subtree
     * if the node has left child,traverse its left child
     * @param t the node that roots the subtree
     * @return node contain the smallest item
     */
    public BinaryNode<AnyType> findMin(BinaryNode<AnyType> t){
        if (t == null)return null;
        else if (t.left == null)return t;
        return findMin(t.left);
    }

    public AnyType findMax(){
        if (isEmpty())throw new BufferUnderflowException();
        return findMax(root).element;
    }
    /**
     * internal method to find the largest item in a subtree
     * @param t the node that roots the subtree
     * @return node contain the largest item
     */
    public BinaryNode<AnyType> findMax(BinaryNode<AnyType> t){
        if (t != null)
            while (t.right != null)
                t = t.right;
        return t;
    }

    public void insert(AnyType x){root = insert(x,root);}
    private BinaryNode<AnyType> insert(AnyType x,BinaryNode<AnyType> t){
        if (t == null)
            return new BinaryNode<>(x,null,null);

        int compareResult = myCompare(x,t.element);

        if (compareResult < 0)
            t.left = insert(x,t.left);
        else if (compareResult > 0)
            t.right = insert(x,t.right);
        else ;//do nothing
        return t;
    }

    /**
     * 需要考虑三种情况：
     * 1. 如果节点是一片树叶，那么可以立即删除
     * 2. 如果节点有一个儿子，那么，被删除的节点的父节点可以直接指向被删除的节点的子节点
     * 3. 如果节点有两个儿子，
     * @param x 需要删除的对象
     */
    public void remove(AnyType x){root = remove(x,root);}
    public BinaryNode<AnyType> remove(AnyType x,BinaryNode<AnyType> t){
        if (t == null)
            return t;//item not found do nothing

        int compareResult = myCompare(x,t.element);

        if (compareResult < 0)
            t.left = remove(x,t.left);
        else if (compareResult > 0)
            t.right = remove(x,t.right);
        else if (t.left!=null && t.right!=null){//item has two children
            t.element = findMin(t.right).element;
            t.right = remove(t.element,t.right);
        }else
            t = (t.left != null)?t.left:t.right;
        return t;
    }

    /*print the tree content in sorted order*/
    public void printTree(){
        if (isEmpty()) System.out.println("Empty Tree");
        else printTree(root);
    }
    /**
     * internal method to print a subtree in sort order
     * @param t the node that roots the subtree
     */
    private void printTree(BinaryNode<AnyType> t){
        if (t != null){
            printTree(t.left);
            System.out.println(t.element);
            printTree(t.right);
        }
    }

    /**
     * internal method to find an item in a subtree
     * @param x is item to search for
     * @param t the node that roots the subtree
     * @return true if the item is found;false otherwise
     */
    private boolean contains(AnyType x,BinaryNode<AnyType> t){
        if (t == null)return false;

        int compareResult = myCompare(x,t.element);

        if (compareResult < 0)return contains(x,t.left);
        else if (compareResult > 0)return contains(x,t.right);
        else return true;
    }
}
